#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OVERFLOW -2
typedef struct
{
    int num;
    int r;
    int c;
    int dir;
}node;
typedef node* ElemType;
typedef struct 
{
    ElemType * base;
    ElemType * top;
    int stack_size;
}SqStack;
typedef int Status;
Status InitStack(SqStack &S)
{
    S.base = (ElemType*)malloc(sizeof(ElemType) * STACK_INIT_SIZE);
    if (!S.base)
        exit(OVERFLOW);
    S.top = S.base;
    S.stack_size = STACK_INIT_SIZE;
    return OK;
}
Status DestroyStack(SqStack &S)
{
    free(S.base);
    return OK;
}
Status ClearStack(SqStack &S)
{
    S.top = S.base;
    return OK;
}
Status StackEmpty(SqStack S)
{
    if (S.base == S.top)
        return TRUE;
    return FALSE;
}
int StackLength(SqStack S)
{
    return S.top - S.base;
}
Status GetTop(SqStack S, ElemType &e)
{
    if (S.base == S.top)
        return ERROR;
    e = *(S.top - 1);
    return OK;
}
Status Push(SqStack &S, ElemType e)
{
    if (S.top - S.base >= STACK_INIT_SIZE)
    {
        S.base = (ElemType*)realloc(S.base, sizeof(ElemType) * (STACK_INIT_SIZE + STACK_INCREMENT));
        if (!S.base)
            exit(OVERFLOW);
        S.top = S.base + S.stack_size;
        S.stack_size += STACK_INCREMENT;
    }
    *S.top++ = e;
    return OK;
}
Status Pop(SqStack &S, ElemType &e)
{
    if (S.base == S.top)
        return ERROR;
    e = *(--S.top);
    return OK;
}

void show(int maze[6][6]);
Status MazePath(int maze[6][6], int row, int col, int src_r, int src_c, int dst_r, int dst_c)
{
    SqStack s;
    InitStack(s);
    int cur_r = src_r;
    int cur_c = src_c;
    int curstep = 1;
    do{
        if (maze[cur_r][cur_c] == 0)
        {
            maze[cur_r][cur_c] = 1;
            show(maze);

            node* cur = (node*)malloc(sizeof(node));
            cur->num = curstep;
            cur->r = cur_r;
            cur->c = cur_c;
            cur->dir = 0;
            Push(s, cur);

            if (cur_r == dst_r && cur_c == dst_c)
                return TRUE;
            
            ++cur_c;

            ++curstep;
        }
        else
        {
            if (!StackEmpty(s))
            {
                node* cur;
                Pop(s, cur);
                while (cur->dir == 4 && !StackEmpty(s))
                {
                    maze[cur_r][cur_c] = 3; // 标记此路块不通
                    show(maze);
                    Pop(s, cur);
                }
                if (cur->dir < 4)
                {
                    ++cur->dir;
                    Push(s, cur);
                    if (cur->dir == 0)
                    {
                        ++cur_c;
                    }
                    else if (cur->dir == 1)
                    {
                        ++cur_r;
                    }
                    else if (cur->dir == 2)
                    {
                        --cur_c;
                    }
                    else if (cur->dir == 3)
                    {
                        ++cur_r;
                    }
                }
            }
        }
    }while (!StackEmpty(s));
    return FALSE;
}
void show(int maze[6][6])
{
    for (int i = 0; i < 6; ++i)
    {
        for (int j = 0; j < 6; ++j)
            printf("%d ", maze[i][j]);
        printf("\n");
    }
    printf("\n");
}
int main(void)
{
    // 0为路，2为墙
    int maze[6][6] = {
        {2, 2, 2, 2, 2, 2},
        {2, 0, 2, 0, 2, 2},
        {2, 0, 0, 0, 2, 2},
        {2, 2, 2, 0, 0, 2},
        {2, 2, 2, 2, 0, 2},
        {2, 2, 2, 2, 2, 2}
    };
    MazePath(maze, 6, 6, 1, 1, 4, 4);

    return 0;
}